package com.zto.sch.advance.algorithms;


/**
 * @program: sch-diy-parent
 * @description:
 * @author: sch
 * @create: 2021-01-17 09:32
 **/
public class InsertSort {
    public static void main(String[] args) {
        int[] arr = {5, 33, 6, 2, 1, -33, 88, 56};
        printArr(arr);
//        Arrays.sort(arr);
//        insertSort1(arr);
        insertSort2(arr);
        printArr(arr);
    }

    /**
     * 思路：认为第一个元素自己是有序的。
     * 1，第一次外循环，让前两个有序。。方法：第二2上与第一个比，小的放在前面
     * 2，第二次循环外循环，让前三个有序。。方法：让第三个在前两个已排序的序列中找到自己的索引位置（从后向前扫描，或扫描出的元素>第三个元素，交换位置）
     * 3，第三次循环外循环，让前四个有序。。。方法同2
     * ....
     * <p>
     * 1,从第一个元素开始，该元素可以认为已经被排序；
     * 2,取出下一个元素，在已经排序的元素序列中从后向前扫描；
     * 3,如果该元素（已排序）大于新元素，将该元素移到下一位置；
     * 4,重复步骤3，直到找到已排序的元素小于或者等于新元素的位置；
     * 5,将新元素插入到该位置后；
     * 6,重复步骤2~5。
     *
     * @param arr
     */
    private static void insertSort1(int[] arr) {
        out:
        for (int i = 1; i <= arr.length - 1; i++) {
            int temp = arr[i];
            in:
            for (int j = i - 1; j >= 0; j--) {
                if (arr[j] > temp) {
                    swapEach(arr, j + 1, j);
                } else {
                    continue out;
                }
            }
        }
    }

    private static void insertSort2(int[] arr) {
        for (int i = 1; i <= arr.length - 1; i++) {
            int temp = arr[i], preIndex = i - 1;
            while (preIndex >= 0 && arr[preIndex] > temp) {
                swapEach(arr, preIndex, preIndex + 1);
                preIndex--;
            }
        }
    }

    private static void swapEach(int[] arr, int j, int i) {
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }

    private static void printArr(int[] arr) {
        for (int a : arr) {
            System.out.print(a + ",");
        }
        System.out.println("");
    }
}
